The present invention relates to parallel data processing systems. More particularly, the present invention relates to parallel data processors of the type comprised of a two-dimensional array of interconnected processing elements which perform arithmetic and logical data processing functions for image processing.
Parallel data processor systems are well adapted to providing effective image processing capabilities. Such parallel image processors typically comprise a two-dimensional matrix-like array of identical digital processing elements. Each processing element is capable of performing a variety of relatively simple logical and arithmetic operations on the data it receives. Each processing element is in turn capable of communication with one or more of its neighboring processing elements. When all processing elements perform their respective simple logical or arithmetic operations on their respective data, the cumulative effect is a much larger and more sophisticated logical/arithmetic operation. Image data may be mapped into the arra of processing elements such that each processing element only receives a portion of the total image data. Thus, sophisticated image processing can be performed upon the image by having the numerous processing elements each perform their own native-mode processing on their respective portions of the overall image. This can have significant speed and cost advantages over a more complex CPU which processes the image data serially.
Image processors frequently employ multiple-instruction/multiple-data (MIMD) class processors. Such processors are complex and nonredundant, i.e., a separate program must be written for each processing element and then the programs must be integrated with one another. This integration process includes the very complex task of ascertaining and programming the absolute addresses of all pixel data needed to be accessed by each individual processing element. This results in long development cycles due to the large number of different complex programs required to be written for a MIMD system. This programming bottleneck is complicated even further when additional processing elements are added to expand a system since more programs must be written and the existing ones typically must be substantially modified. Furthermore, the separate programs must be reintegrated, including redetermining the absolute addresses of pixel data needed by each program. Moreover, the programming associated with interprocessor communications severely limits the efficiency of MIMD processors as the number of processing elements increases.
Single-instruction/multiple-data (SIMD) class processsors have also been employed in parallel processing systems. A SIMD class processor is much less complex than a MIMD class processor because only a single program need be written for simultaneous execution by all processing elements. However, the very complex task remains of programming the addresses of all pixel data needed to be accessed by the processing elements during program execution, plus reprogramming the addresses when processing elements are added to expand the system.
A further problem in applying massively parallel processing (MIMD and SIMD) to image processing relates to problems in the efficient routing of image data through the parallel processing system. The digital data on which the processing elements operate is typically received and sent out on separate input and output data buses. The data buses in a typical SIMD image processor are "bit-plane mapped," i.e., single bits representing portions of multiple pixels within the image are available in parallel. However, most sensors which supply images to be processed, as well as most display devices which display such images, operate with "pixel-mapped" data, i.e., data wherein all bits representing a single pixel within the image are available in parallel. Therefore, bit-plane mapped SIMD image processors require dedicated hardware, programming and/or processing time to convert the data from pixel format to bit-plane format and back again. This in turn increases the cost and reduces the speed of such conventional SIMD image processors.
Accordingly, parallel image processing systems have failed to fully exploit the cost and speed efficiencies potentially available in massively parallel architecture and suffer from complex user programming problems.